package leetcode_121_140;

public class solve_130 {
    /**
     *给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O'
     * 找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
     */
    public void solve(char[][] board) {
        /**
         * 想法从最外围的一圈中含有的O作为起点，与其相连的O都是不用变化的
         * 1ms
         */
        int m=board.length,n=board[0].length;
        //标记单元格是否已经被处理过，0代表未处理过，1代表已经处理过
        int[][] isSolved=new int[m][n];
        //四条边寻找O进行递归判断
        for (int i = 0; i < m; i++) {       //左右列
            if(board[i][0]=='O' && isSolved[i][0]!=1)
                function(board,isSolved,i,0);
            if(board[i][n-1]=='O' && isSolved[i][n-1]!=1)
                function(board,isSolved,i,n-1);
        }
        for (int i = 0; i < n; i++) {        //上下行
            if(board[0][i]=='O' && isSolved[0][i]!=1)
                function(board,isSolved,0,i);
            if(board[m-1][i]=='O' && isSolved[m-1][i]!=1)
                function(board,isSolved,m-1,i);
        }
        //未处理过的O变为X
        for (int i = 0; i < m; i++)
            for (int t= 0; t< n; t++)
                if(board[i][t]=='O' && isSolved[i][t]==0)
                    board[i][t]='X';
    }

    /**
     * 递归寻找相连的位置
     * @param board 矩阵
     * @param isSolved 记录处理过的位置
     * @param m 当前的横坐标
     * @param n 当前的纵坐标
     */
    void function(char[][] board,int[][] isSolved,int m,int n){
        if(board[m][n]=='O'){  //如果相连着的当前位置为O，直接进行处理
            isSolved[m][n]=1;

            if( m != 0 && isSolved[m-1][n]!=1)
                function(board,isSolved,m-1,n);  //向上寻找
            if( m != board.length-1 && isSolved[m+1][n]!=1)
                function(board,isSolved,m+1,n);  //向下寻找
            if( n != 0 && isSolved[m][n-1]!=1)
                function(board,isSolved,m,n-1);  //向左寻找
            if( n != board[0].length-1 && isSolved[m][n+1]!=1)
                function(board,isSolved,m,n+1);  //向右寻找
        }
    }
}
